SQUFOF

即 Shanks 的平方型分解算法。当要分解的数的两个素因数比较近时这个算法跑得很快。

It's Shanks' Square Form Factorization method. It's quite fast when the two prime factors of the number that needs to be factorized are quite near.

不知道如果两个素因子差为 $m$$m$，那么时间复杂度是否为 $O(\sqrt{m})$$O(\sqrt{m})$。反正这个算法运算量有一个精确上界 $3\sqrt{2\sqrt{n}}$$3\sqrt{2\sqrt{n}}$（还要再乘以一个常数，视实现决定）。

It's unknown that if $m$$m$ is the subtraction result of the two prime factors, then the time complexity is $O(\sqrt{m})$$O(\sqrt{m})$. But this algorithm has an precise computing upper bound of $3\sqrt{2\sqrt{n}}$$3\sqrt{2\sqrt{n}}$ (It should be multiplied with a constant which depends on the implementation).

__uint128_t squfof(__uint128_t value) {
    __uint128_t s = sqrtl(1.0l * value) + 1e-6;
    while (s * s > value) s--;
    if (s * s == value) return s;
    __int128 d, po, p, p_prev, q, q_prev, q_, b, r;
    long long l, b_, i;
    int k = 0;
    l = 2 * sqrtl(2.0l * s);
    b_ = 3 * l;
    while (++k) {
        d = k * value;
        po = p_prev = p = sqrtl(1.0l * d);
        q_prev = 1;
        q = d - po * po;
        while (q < 0) {
            po--;
            p_prev--;
            p--;
            q = d - po * po;
        }
        if (!q) return gcd(value, k);
        for (i = 2; i < b_; i++) {
            b = (po + p) / q;
            p = b * q - p;
            q_ = q;
            q = q_prev + b * (p_prev - p);
            r = sqrtl(1.0 * q) + 1e-6;
            if (!(i & 1) && r * r == q) break;
            q_prev = q_;
            p_prev = p;
        }
        if (i >= b_) continue;
        b = (po - p) / r;
        p_prev = p = b * r + p;
        q_prev = r;
        q = (d - p_prev * p_prev) / q_prev;
        i = 0;
        do {
            b = (po + p) / q;
            p_prev = p;
            p = b * q - p;
            q_ = q;
            q = q_prev + b * (p_prev - p);
            q_prev = q_;
            i++;
        } while (p != p_prev && i < b_);
        if (i >= b_) continue;
        r = gcd(value, q_prev);
        if (r != 1) return r;
    }
    return 0;
}